/**
 * 
 */
package net.sf.tools.uiconfig.util;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

import net.sf.tools.uiconfig.model.Menu;


/**
 * @author Sabuj Das | sabuj.das@gmail.com
 *
 */
public class ListTree<T extends HierarchicalEntity<T>> implements Tree<T> {

	private static class Node{
		int index;
		Node parent;
		Map<Integer, Node> children = new HashMap<Integer, Node>();
		boolean isLeaf = true;
		
		public Node(int index) {
			this.index = index;
		}

		public Node(int index, boolean isLeaf) {
			this.index = index;
			this.isLeaf = isLeaf;
		}
		
		public void addChield(Node chield){
			children.put(chield.index, chield);
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + index;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj) {
				return true;
			}
			if (obj == null) {
				return false;
			}
			if (!(obj instanceof Node)) {
				return false;
			}
			Node other = (Node) obj;
			if (index != other.index) {
				return false;
			}
			return true;
		}
		
		@Override
		public String toString() {
			return "Node [index=" + index + "]";
		}

		public boolean hasChildren(){
			return (null != children && !children.isEmpty());
		}
	}
	
	private final List<T> originalData;
	private Map<T, Integer> originalDataIndexMap = new HashMap<T, Integer>();
	private Node root ;
	
	public ListTree(List<T> originalData) {
		this.originalData = originalData;
		root = new Node(-1, false);
		buildTree();
	}

	/**
	 * 
	 */
	private void buildTree() {
		if(null == originalData)
			return;
		//  2*n < n*n for any n > 2
		for (int i = 0; i < originalData.size(); i++){
			T item = originalData.get(i);
			originalDataIndexMap.put(item, i);
		}
		
		for (int i = 0; i < originalData.size(); i++) {
			T item = originalData.get(i);
			if(null != item.getParent())
				continue;
			
			Node node = new Node(i);
			if(item.hasChildren()){
				node.isLeaf = false;
				buildSubTree(node, item);
			}
			node.parent = root;
			root.addChield(node);
			
		}
		
	}

	
	
	/**
	 * 2*n < n*n for any n > 2
	 * @param node
	 * @param item
	 */
	private void buildSubTree(Node node, T item) {
		for (T chieldItem : item.getChildren()) {
			Node chieldNode = new Node(originalDataIndexMap.get(chieldItem));
			if(chieldItem.hasChildren()){
				chieldNode.isLeaf = false;
				buildSubTree(chieldNode, chieldItem);
			}
			chieldNode.parent = node;
			node.addChield(chieldNode);
		}
	}

	/**
	 * @param root
	 * @param parentIndex
	 * @return
	 */
	private Node findParentNode(Node root, final int parentIndex) {
		if(root.hasChildren()){
			Set<Integer> keys = root.children.keySet();
			for (Integer index : keys) {
				if(parentIndex == index){
					return root.children.get(index);
				}
				return findParentNode(root.children.get(index), parentIndex);
			}
		}
		return null;
	}

	
	public T get(int index) {
		return originalData.get(index);
	}
	
	public List<T> getChildren(T item) {
		int index = originalDataIndexMap.get(item);
		if(index < 0)
			return null;
		return item.getChildren();
	}

	public static void main(String[] args) {
		List<Menu> menus = new ArrayList<Menu>();
		Menu m1 = new Menu();
		m1.setMenuName("M_1");
		Menu m2 = new Menu();
		m2.setMenuName("M_2");
		Menu m3 = new Menu();
		m3.setMenuName("M_3");
		Menu m4 = new Menu();
		m4.setMenuName("M_4");
		Menu m5 = new Menu();
		m5.setMenuName("M_5");
		Menu m6 = new Menu();
		m6.setMenuName("M_6");
		Menu m7 = new Menu();
		m7.setMenuName("M_7");
		Menu m8 = new Menu();
		m8.setMenuName("M_8");
		Menu m9 = new Menu();
		m9.setMenuName("M_9");
		Menu m10 = new Menu();
		m10.setMenuName("M_10");
		
		m4.setParentMenu(m1);
		m7.setParentMenu(m1);
		m1.getChildren().add(m4);
		m1.getChildren().add(m7);
		
		
		m2.setParentMenu(m3);
		m5.setParentMenu(m3);
		m6.setParentMenu(m3);
		m3.getChildren().add(m2);
		m3.getChildren().add(m5);
		m3.getChildren().add(m6);
		
		m8.setParentMenu(m7);
		m9.setParentMenu(m7);
		m10.setParentMenu(m7);
		m7.getChildren().add(m8);
		m7.getChildren().add(m9);
		m7.getChildren().add(m10);
		
		menus.add(m1);
		menus.add(m2);
		menus.add(m3);
		menus.add(m4);
		menus.add(m5);
		menus.add(m6);
		menus.add(m7);
		menus.add(m8);
		menus.add(m9);
		menus.add(m10);
		
		Tree<Menu> tree = new ListTree<Menu>(menus);
		System.out.println("Done");
	}
	
}
